package own.stu.jobgib.playown.alg.solution;

/**
 * 对 [1,2,3,4,5,6] 来说，其前缀和可以是 pre=[1,3,6,10,15,21]
 * 可以使用公式 pre[𝑖]=pre[𝑖−1]+nums[𝑖]得到每一位前缀和的值，从而通过前缀和进行相应的计算和解题
 */
public class NumSubarray {

    public static void main(String[] args) {
        NumSubarray a = new NumSubarray();
//        System.out.println(a.countSubArray(new int[]{3, 4, 5}));
//        System.out.println(a.countSubArray_2(new int[]{3, 4, 5}));
//        System.out.println(a.atMostK(3, new int[]{1, 3, 4}));
//        System.out.println(a.exactK(3, new int[]{1, 3, 4}));

//        System.out.println(a.findSubstringInWraproundString("zab"));
        System.out.println(a.numSubarrayBoundedMax(new int[]{2, 1, 4, 3}, 2, 3));
    }

    /*
     * 如果让你求一个数组的连续子数组总个数，你会如何求？其中连续指的是数组的索引连续。
     *  比如 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你需要返回 6。
     *
     * think : 一种思路是总的连续子数组个数等于：
     * 以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + ... + 以索引为 n - 1 结尾的子数组个数
     *
     * 而由于以索引为 i 结尾的子数组个数就是 i + 1，因此这道题可以直接用等差数列求和公式 (1 + n) * n / 2，其中 n 数组长度。
     */
    public int countSubArray(int[] nums) {
        int ans = 0;
        int pre = 0;
        for (int i : nums) {
            pre += 1;
            ans += pre;
        }
        return ans;
    }

    /**
     * 如果让你求一个数组相邻差为 1 连续子数组的总个数呢？其实就是索引差 1 的同时，值也差 1。
     */
    public int countSubArray_2(int[] nums) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] + 1) {
                pre += 1;
            } else {
                pre = 0;
            }
            ans += pre;
        }
        return ans;
    }

    /**
     * 如果让你求出不大于 k 的子数组的个数呢？
     * 不大于 k 指的是子数组的全部元素都不大于 k。
     * 比如 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，
     * 不大于 3 的子数组有 [1], [3], [1,3] ，那么 [1,3,4] 不大于 3 的子数组个数就是 3。
     */

    public int atMostK(int k, int[] nums) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] <= k) {
                pre += 1;
            } else {
                pre = 0;
            }
            ans += pre;
        }
        return ans;
    }

    /**
     * 如果让你求出子数组最大值刚好是 k 的子数组的个数呢？
     * 比如 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，
     * 子数组最大值刚好是 3 的子数组有 [3], [1,3] ，
     * 那么 [1,3,4] 子数组最大值刚好是 3 的子数组个数就是 2。
     * <p>
     * 实现函数 exactK(k, nums)。
     * <p>
     * 实际上是 exactK 可以直接利用 atMostK，即 atMostK(k) - atMostK(k - 1)
     */
    public int exactK(int k, int[] nums) {
        return atMostK(k, nums) - atMostK(k - 1, nums);
    }

    /**
     * 如果我让你求出子数组最大值刚好是 介于 k1 和 k2 的子数组的个数呢？实现函数 betweenK(k1, k2, nums)。
     * <p>
     * 实际上是 betweenK 可以直接利用 atMostK，即 atMostK(k1, nums) - atMostK(k2 - 1, nums)，其中 k1 > k2。
     * 前提是值是离散的， 比如上面我出的题都是整数。 因此我可以直接 减 1，因为 1 是两个整数最小的间隔。
     * <p>
     * betweenK(5, 10)
     * 小于等于 10 的区域减去 小于 5 的区域就是 大于等于 5 且小于等于 10 的区域。
     * <p>
     * 注意说的是小于 5， 不是小于等于 5。
     * 由于整数是离散的，最小间隔是 1。
     * 因此小于 5 在这里就等价于 小于等于 4。
     * 这就是 betweenK(k1, k2, nums) = atMostK(k1) - atMostK(k2 - 1) 的原因。
     * <p>
     * 因此不难看出 exactK 其实就是 betweenK 的特殊形式。 当 k1 == k2 的时候， betweenK 等价于 exactK。
     */
    public int betweenK(int k1, int k2, int[] nums) { //k1 > k2
        return atMostK(k1, nums) - atMostK(k2 - 1, nums);
    }

    /**
     * application:
     * <p>
     * 把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，
     * 所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". 
     * <p>
     * 现在我们有了另一个字符串 p 。
     * 你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，
     * 你需要输出字符串 s 中 p 的不同的非空子串的数目。 
     * <p>
     * 注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。
     */
    public int findSubstringInWraproundString(String p) {
        char[] cs = p.toCharArray();
        int ans = 0, pre = 0;
        int[] lenMap = new int[26];

        for (int i = 0; i < cs.length; i++) {
            if (i > 0 && (cs[i] == cs[i - 1] + 1 || cs[i] == cs[i - 1] - 25)) {
                pre += 1;
            } else {
                pre = 1;
            }
            int idx = cs[i] - 'a';
            lenMap[idx] = Math.max(lenMap[idx], pre);
        }

        for (int v : lenMap) {
            ans += v;
        }

        return ans;
    }

    /**
     * 给定一个元素都是正整数的数组 A ，正整数 L  以及  R (L <= R)。
     * <p>
     * 求连续、非空且其中最大元素满足大于等于 L  小于等于 R 的子数组个数。
     * <p>
     * 例如 :
     * 输入:
     * A = [2, 1, 4, 3]
     * L = 2
     * R = 3
     * 输出: 3
     * 解释: 满足条件的子数组: [2], [2, 1], [3].
     * 注意:
     * <p>
     * L, R  和  A[i] 都是整数，范围在  [0, 10^9]。
     * 数组  A  的长度范围在[1, 50000]。
     */
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        if (nums == null || nums.length == 0 || left > right) {
            return 0;
        }

        return notGreaterThan(right, nums) - notGreaterThan(left - 1, nums);
    }

    private int notGreaterThan(int k, int[] nums) {
        int ans = 0, pre = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= k) {
                pre += 1;
            } else {
                pre = 0;
            }
            ans += pre;
        }
        return ans;
    }
}
